﻿#pragma once

#include <iostream>
#include <vector>
#include <algorithm>

#include <time.h>
#include <assert.h>
#include <unordered_map>
#include <thread>
#include <mutex>

using std::cout;
using std::endl;

#ifdef _WIN32
#include <windows.h>
#else
// ...
#endif

static const size_t MAX_BYTES = 256 * 1024;
static const size_t NFREE_LISTS = 208;
static const size_t NPAGES = 129; //pagecache直接映射
static const size_t PAGE_SHIFT = 13; //一个页大小为8KB

#ifdef _WIN64
typedef unsigned long long PAGE_ID;
#elif _WIN32
typedef size_t PAGE_ID;
#else
// linux
#endif

// 直接去堆上按页申请空间
inline static void* SystemAlloc(size_t kpage)
{
#ifdef _WIN32
	void* ptr = VirtualAlloc(0, kpage << 13, MEM_COMMIT | MEM_RESERVE, PAGE_READWRITE);
#else
	// linux下brk mmap等
#endif

	if (ptr == nullptr)
		throw std::bad_alloc();

	return ptr;
}

inline static void SystemFree(void* ptr)
{
#ifdef _WIN32
	VirtualFree(ptr, 0, MEM_RELEASE);
#else
	// sbrk unmmap等
#endif
}

// 传引用返回
static void*& NextObj(void* obj)
{
	return *(void**)obj;
}


// 管理切分好的小对象的自由链表
class FreeList
{
public:
	void Push(void* obj)
	{
		assert(obj);

		// 头插
		//*(void**)obj = _freeList;
		NextObj(obj) = _freeList;
		_freeList = obj;
		++_size;
	}

	void PushRange(void* start, void* end, size_t n)
	{
		NextObj(end) = _freeList;
		_freeList = start;
		_size += n;
	}

	void PopRange(void*& start, void*& end, size_t n)
	{
		// 自由链表下面的小内存块必须大于一次批量取出的内存块
		assert(n <= _size);
		start = _freeList;
		end = start;

		for (size_t i = 0; i < n - 1; i++)
		{
			end = NextObj(end);
		}
		_freeList = NextObj(end);
		NextObj(end) = nullptr;
		_size -= n;
	}


	void* Pop()
	{
		assert(_freeList);

		// 头删
		void* obj = _freeList;
		_freeList = NextObj(obj);
		--_size;
		return obj;
	}

	bool Empty()
	{
		return _freeList == nullptr;
	}

	// 需要传引用返回
	size_t& Maxsize()
	{
		return _maxSize;
	}

	size_t Size()
	{
		return _size;
	}

private:
	void* _freeList = nullptr;
	size_t _maxSize = 1;
	size_t _size = 0;
};

// 计算对象大小的对齐映射规则
class SizeClass
{
public:
	// 整体控制在最多10%左右的内碎片浪费
	// [1,128]					8byte对齐	    freelist[0,16)
	// [128+1,1024]				16byte对齐	    freelist[16,72)
	// [1024+1,8*1024]			128byte对齐	    freelist[72,128)
	// [8*1024+1,64*1024]		1024byte对齐     freelist[128,184)
	// [64*1024+1,256*1024]		8*1024byte对齐   freelist[184,208)

	//size_t _RoundUp(size_t bytes, size_t alignNum)
	//{
	//	size_t alignSize = 0;
	//	if (bytes % alignNum != 0)
	//	{
	//		// 有余数，需要向上取整一个,然后再乘以对齐数
	//		alignSize = (bytes / alignNum + 1) * alignNum;
	//	}
	//	else
	//	{
	//		// 没有余数，此时bytes就是对齐数
	//		alignSize = bytes;
	//	}
	//}
	// 静态和内联
	// 内联是减少调用成本
	static inline size_t _RoundUp(size_t bytes, size_t alignNum)
	{
		// 这里我们可以解释一下，alignNum以8为例，alignNum-1取反比特位第三之前都是1
		// alignNum以8,此时bytes + alignNum - 1的范围在8-15 
		// 这个范围的数 第四位都是1，第四位之前都是0，第四位之后无论是什么都会置0
		// 所以最后只有比特位为4的是1，而这个值就是8
		return ((bytes + alignNum - 1) & ~(alignNum - 1));
	}
	// 静态是不需要对象调用，直接类名调用即可
	// 如果RoundUp适用static修饰，_RoundUp也必须使用静态
	// 因为静态成员函数没有this指针，无法调用非静态成员函数
	// 给你一个字节数，按照对齐数进行对齐
	// 7 - 8 
	// 12 - 16
	static inline size_t RoundUp(size_t size)
	{
		if (size <= 128)
		{
			return _RoundUp(size, 8);
		}
		else if (size <= 1024)
		{
			return _RoundUp(size, 16);
		}
		else if (size <= 8 * 1024)
		{
			return _RoundUp(size, 128);
		}
		else if (size <= 64 * 1024)
		{
			return _RoundUp(size, 1024);
		}
		else if (size <= 256 * 1024)
		{
			return _RoundUp(size, 8 * 1024);
		}
		else
		{
			return _RoundUp(size, 1 << PAGE_SHIFT);
		}
	}

	// 求size对应在哈希表中的下标
	//static inline size_t _Index(size_t bytes, size_t alignNum)
	//{			
	//	if (bytes % alignNum == 0)
	//	{
	//		// 此时没有余数，需要减一
	//		return bytes / alignNum - 1;
	//	}
	//	else
	//	{
	//		// 如果有余数，直接除即可
	//		return bytes / alignNum;
	//	}
	//}

	//这里align_shift是指对齐数的二进制位数。比如size为2的时候对齐数为8，8就是2^3，所以此时align_shift就是3
	static inline size_t _Index(size_t bytes, size_t align_shift)
	{
		// 这里的以对齐数为8的例子，那么此时align_shift就是3
		// size + (1 << align_shift) - 1)的范围为[8，15]
		// 这个范围的值除一对齐数就是1
		// 减一是为了对应数组下标从0开始
		return ((bytes + (1 << align_shift) - 1) >> align_shift) - 1;
		// 这里_Index计算的是当前size所在区域的第几个下标，所以Index的返回值需要加上前面所有区域的哈希桶的个数
	}

	// 计算映射的哪一个自由链表桶
	static inline size_t Index(size_t bytes)
	{
		assert(bytes <= MAX_BYTES);

		// 每个区间有多少个链
		static int group_array[4] = { 16, 56, 56, 56 };
		if (bytes <= 128) {
			// [1,128] 8B -->8B就是2^3B，对应二进制位为3位
			return _Index(bytes, 3);// 3是指对齐数的二进制位位数，这里8B就是2^3B，所以就是3
		}
		// 由于[1,128]是按照8字节对齐，但是[128+1,1024] 是按照16字节对齐，规则不一样
		// 所以现在来了一个139的字节，需要分成两段
		// 前[1,128]是按照8字节对齐，[128+1,1024] 是按照16字节对齐
		// 此时肯定大于128，所以需要加上前16个桶，再加上现在的下标即可
		else if (bytes <= 1024) {
			return _Index(bytes - 128, 4) + group_array[0];
		}
		else if (bytes <= 8 * 1024) {
			return _Index(bytes - 1024, 7) + group_array[1] + group_array[0];
		}
		else if (bytes <= 64 * 1024) {
			return _Index(bytes - 8 * 1024, 10) + group_array[2] + group_array[1] + group_array[0];
		}
		else if (bytes <= 256 * 1024) {
			return _Index(bytes - 64 * 1024, 13) + group_array[3] + group_array[2] + group_array[1] + group_array[0];
		}
		else {
			assert(false);
		}

		return -1;
	}

	// 一次thread cache从中心缓存获取多少个
	static size_t NumMoveSize(size_t size)
	{
		assert(size > 0);

		// [2, 512]，一次批量移动多少个对象的(慢启动)上限值
		// 小对象一次批量上限高
		// 小对象一次批量上限低
		int num = MAX_BYTES / size;
		if (num < 2)
			num = 2;

		if (num > 512)
			num = 512;

		return num;
	}

	// 计算一次向系统获取几个页
	// 单个对象 8byte
	// ...
	// 单个对象 256KB
	static size_t NumMovePage(size_t size)
	{
		size_t num = NumMoveSize(size);
		size_t npage = num * size;

		npage >>= PAGE_SHIFT;
		if (npage == 0)
			npage = 1;

		return npage;
	}
};

// 管理多个连续页大块内存跨度结构
struct Span
{
	// 进程的地址的空间大小为2^32 = 4GB
	// 一页的大小差不多就有8KB
	// 那么此时就有2^19页
	// 64位平台下进程的地址的空间大小为2^64
	// 此时就有2^51页，此时页号用size_t存储不下
	// 此时需要使用条件编译
	PAGE_ID _pageId = 0; // 大块内存起始页的页号
	size_t  n = 0;      // 页的数量

	Span* _next = nullptr;	// 双向链表的结构
	Span* _prev = nullptr;

	size_t _objSize = 0; // 切好的小对象的大小
	size_t _useCount = 0; // 切好小块内存，被分配给thread cache的计数
	void* _freeList = nullptr;  // 切好的小块内存的自由链表

	bool _isUse = false; // 表示当前span是否正在被使用
};

// 带头双向循环链表 
class SpanList
{
public:
	SpanList()
	{
		_head = new Span;
		_head->_next = _head;
		_head->_prev = _head;
	}
	
	Span* Begin()
	{
		return _head->_next;
	}

	Span* End()
	{
		return _head;
	}

	bool Empty()
	{
		return _head->_next == _head;
	}

	void PushFront(Span* span)
	{
		Insert(Begin(), span);
	}

	Span* PopFront()
	{
		Span* front = _head->_next;
		Erase(front);
		return front;
	}
	// 找PageCache申请的span
	// 在pos位置之前插入
	void Insert(Span* pos, Span* newSpan)
	{
		assert(pos);
		assert(newSpan);

		Span* prev = pos->_prev;
		// prev newspan pos
		prev->_next = newSpan;
		newSpan->_prev = prev;
		newSpan->_next = pos;
		pos->_prev = newSpan;
	}

	void Erase(Span* pos)
	{
		assert(pos);
		assert(pos != _head);
		
		Span* prev = pos->_prev;
		Span* next = pos->_next;

		prev->_next = next;
		next->_prev = prev;
	}

private:
	Span* _head;
public:
	std::mutex _mux; // 桶锁
};